介绍

转化为强化学习的问题

State evaluation目标：走新路总时间比老路少

1. state(s)：

小路，高速路

2. reward(r)：

路上需要的时间（越少越好）

3. action(A)：

action:选择进入哪条路（这里只能选两段）

3. episode：

走一次的路程

数学表示

已知：s1=小路， s2 = 高速路； r(s1),r(s2)
求：v(s1), v(s2)

需要的实验数据：

总时间？

每段路的时间？

–r(s_i)

Model(free) 不需要模型的强化学习

1
2
3
4
5
6

相对于老路，同等路程节约的时间
     R(小路)         R(高速路)
周一    -5             6
周二    -8             9
周三    -2             8
周四    -3             2

主观的value(s)

算法一： R = mean(R_k)

算法二： 一步步往上爬。

逐步更新： V_k+1 = V_k + α*（R_k+1 - V_k)

注：k表示每个episode

k=0时，实验比老路快0分钟，V_1=0预期 V_k=0

k=1, 实验比老路快6分钟，V_1=6 , R1-V0=6, a=0.5, V_2=3，下一次预期3.

k=2, 实验比老路快9分钟，V_2=9 , R2-V1=6, a=0.5, V_3=6，下一次预期6.

k=3, 实验比老路快8分钟，V_3=8 , R3-V2=2, a=0.5, V_3=7，下一次预期7.

k=4, 实验比老路快2分钟，V_2=2 , R2-V1=-5, a=0.5, V_3=4.5，下一次预期4.5.
.
.

1
2
3
4
5
6
7

相对于老路，同等路程节约的时间
        V_k         R_k+1 - V_k    V_k+1
预测     0                           0
周一     6             6            3
周二     9             6            6
周三     8             2            7
周四     2             -5           4.5

两种算法的比较

features of delta rule

1.learning rate is arbitray

2. delta rule更重视新经验

3. delta relu只存储一个变量 V_k+1

面向未来

主观的value(s)

算法三：面向未来

V_k+1 = V_k + α*Δ

Δ = [R(s) + γV(s’)] - V(s) # s’下一个state

注：k表示每个episode / γ=1 / α = 1

k=0时，走小路0分钟，走高速路0分钟，Δ= 0 V_1=0 预 期 V（小路）=0 ，v(高速路)=0

k=1, 走小路实际比之前慢-5，R(s)=-5,V(s’)=0,V(s)=0，Δ=-5, V_2 =-5，期望下次走小路是-5. 高速路没有下一个状态，Δ= R(s)-V(S)=6,V_2=6，也就是下次预期为6.

k=2, 走小路实际比之前慢-8，R(s)=-8,V(s’)=6,V(s)=-5，Δ=-7, V_3 =-12，期望下次走小路是-12. 高速路没有下一个状态，Δ= R(s)-V(S)=9-6,V_3=3，也就是下次预期为3.

k=3, 走小路实际比之前慢-2，R(s)=-2,V(s’)=3,V(s)=-12，Δ=-11, V_4 =-23，期望下次走小路是-23. 高速路没有下一个状态，Δ= R(s)-V(S)=8-3,V_4=5，也就是下次预期为5.

k=4, 走小路实际比之前慢-3，R(s)=-3,V(s’)=5,V(s)=-23，Δ=-21, V_5 =-44，小路是-44. 高速路没有下一个状态，Δ= R(s)-V(S)=2-5,V_5=-3，也就是预期为-3.

1
2
3
4
5
6
7

相对于老路，同等路程节约的时间
        R(小路)       R(高速路)   V(小路)    V(高速路)
预测                                0         0
周一     -5            6            -5        6
周二     -8            6            -12       3
周三     -2            8            -23       5
周四     -3            2            -44      -3

TD　learning(temporal-difference learning)

时间差分预测

V(St) = V(St) + α[Rt+1 + γV(St+1) - V(St)]

注：Rt+1 + γV(St+1)被称作TD target项，Rt+1 + γV(St+1) - V(St)被称作TD error项。

代码实现

1
2

import numpy as np 
import matplotlib.pyplot as plt

1
2
3
4
5
6
7
8
9
10
11
12

# problem set-up #客观环境
def next_s(s):
    if s==0:
        return 1 
    else:
        return -1 #terminal

def reward(s):
    if s==0:
        return np.random.normal(-2,1)
    elif s == 1:
        return np.random.normal(5,1)

1
2
3
4

# learning set-up #主观设置
A = .5 # learning rate
gamma =1 # no temporal discount

1
2
3
4
5
6
7
8
9
10
11
12

V = np.zeros(2) # initialize to 0

Nepis = 10
for k in range(Nepis):
    s=0 

    while s !=-1:
        s_new = next_s(s)
        pred_err = reward(s) + gamma * V[s_new] -V[s]
        V[s] = V[s] +A * pred_err
        s = s_new
    print(V)

[-0.42162329  2.10378408]
[-0.87091793  4.43746472]
[0.28692157 6.39314193]
[1.54135436 8.42799535]
[ 4.2044904  10.89704813]
[ 6.51560519 13.1345473 ]
[ 8.36096536 16.35348595]
[10.67874611 18.51504203]
[13.31509973 20.74217751]
[15.92313128 22.25555239]

1